import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author : xwj
 * @date : 2021/9/12 22:19
 * @description : 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *                  有效字符串需满足：
 *                      左括号必须用相同类型的右括号闭合。
 *                      左括号必须以正确的顺序闭合。
 * @class : test20
 **/

public class test20 {

    //1. 1 ms	36.3 MB
    //将左括号存入数组，碰到右括号将数组中最后一个移除数组，如果配对则继续，否则直接返回错误，最后判断数组是否为空
    public static boolean isValid(String s) {
        int len = s.length();
        if (len % 2 == 1) {
            return false;
        }
        boolean res = true;
        List<Character> tmp = new ArrayList<>();
        char c;
        for (int i = 0; i < len; i++) {
            c = s.charAt(i);
            switch (c) {
                case '{' :
                    tmp.add('{');
                    break;
                case '[' :
                    tmp.add('[');
                    break;
                case '(' :
                    tmp.add('(');
                    break;
                case '}' :
                    int l = tmp.size();
                    if (l == 0) {
                        return false;
                    }
                    c = tmp.remove(l - 1);
                    if (c != '{') {
                        return false;
                    }
                    break;
                case ']' :
                    l = tmp.size();
                    if (l == 0) {
                        return false;
                    }
                    c = tmp.remove(l - 1);
                    if (c != '[' ) {
                        return false;
                    }
                    break;
                case ')' :
                    l = tmp.size();
                    if (l == 0) {
                        return false;
                    }
                    c = tmp.remove(l - 1);
                    if (c != '(') {
                        return false;
                    }
                    break;
            }
        }
        if (tmp.size() != 0) {
            res = false;
        }
        return res;
    }

    //2. 1 ms	36 MB
    //将左括号存入栈中，遇到右括号时，出栈并判断是否匹配，最后判断栈是否为空
    public static boolean isValid2(String s) {
        Deque<Character> stack = new LinkedList<>();
        int len = s.length();
        if (len == 0 || len % 2 == 1) {
            return false;
        }
        for (int i = 0; i < len; i ++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty() || !check(stack.pop(), c)) {
                    return false;
                }
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }

    public static boolean check(char c1, char c2){
        if (c1 == '(' && c2 == ')') {
            return true;
        }
        if (c1 == '[' && c2 == ']') {
            return true;
        }
        if (c1 == '{' && c2 == '}') {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String s = "{()}";
        System.out.println(isValid2(s));
    }

}
